package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 递归和迭代共两招。
 */
public class _889_make_tree_pre_post {
    
    class ok {
        /**
         * 蒙对溜~
         * */
        Map<Integer, Integer> postIndex = new HashMap<>();
        public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
            int n = preorder.length;
            for (int i = 0; i < n; i++) {
                postIndex.put(postorder[i], i);
            }
            return make(preorder, 0, n - 1, postorder, 0, n - 1);
        }
        TreeNode make(int[] preorder, int prel, int prer, int[] postorder, int postl, int postr) {
            if (prel > prer) return null;
            TreeNode root = new TreeNode(preorder[prel]);
            if (prer == prel) return root;
            int llen = postIndex.get(preorder[prel + 1]) - postl + 1;
            root.left = make(preorder, prel + 1, prel + llen, postorder, postl, postl + llen - 1);
            root.right = make(preorder, prel + llen + 1, prer, postorder, postl + llen, postr - 1);
            return root;
        }
    }
    
    /**
     * 骚套路真是一个接一个！
     * */
    class of1 {
        int[] pre, post;
        Map<Integer, Integer> postMap = new HashMap<>();
        public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
            pre = preorder;
            post = postorder;
            int n = preorder.length;
            for (int i = 0; i < n; i++) {
                postMap.put(postorder[i], i);
            }
            return make(0,0, n);
        }
        /**
         * @param preIndex 前序子树开始位置
         * @param postIndex 后续子树开始位置
         * @param n 当前子树长度
         * */
        TreeNode make(int preIndex, int postIndex, int n) {
            if (n == 0) return null;
            TreeNode root = new TreeNode(pre[preIndex]);
            if (n == 1) return root;
            int llen = postMap.get(pre[preIndex + 1]) - postIndex + 1;
            root.left = make(preIndex + 1, postIndex, llen);
            root.right = make(preIndex + llen + 1, postIndex + llen, n - llen - 1);
            return root;
        }
    }
    
    /*
     * 官方没给迭代解法，一个屄友给出了迭代和递归，递归和我想的不一样
     * 他这个很简洁，效率应该不高，但我不知道该怎么分析！
     *
     * 这个也很像官方的递归方法，一开始两个索引下标都从 0 开始，然后增加
     *
     * 咋分析它的复杂度呢？
     *
     * 居然还很快？？？？
     *
     * */
    class bi_yo {
        int pre, post;
        public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
            TreeNode root = new TreeNode(preorder[pre++]);
            if (postorder[post] != root.val)
                root.left = constructFromPrePost(preorder, postorder);
            if (postorder[post] != root.val)
                root.right = constructFromPrePost(preorder, postorder);
            post++;
            return root;
        }
    }
    
    class cunt2 {
        public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
            TreeNode root = new TreeNode(preorder[0]);
            LinkedList<TreeNode> stack = new LinkedList<>();
            stack.push(root);
            for (int i = 1, j = 0; i < preorder.length; i++) {
                while (!stack.isEmpty() && stack.peek().val == postorder[j]) {
                    stack.pop();
                    j++;
                }
                TreeNode node = new TreeNode(preorder[i]);
                if (stack.peek().left == null) stack.peek().left = node;
                else stack.peek().right = node;
                stack.push(node);
            }
            return root;
        }
    }
}
